In mobile wireless networks and in the Internet, each router must keep informed of the neighboring routers with which it can establish bi-directional communications using a neighbor discovery protocol. Many existing neighbor discovery protocols have excessive communication overhead, and thus consume excessive bandwidth in networks with limited bandwidth. There remains, therefore, a need for an improved neighbor discovery protocol that can efficiently establish bi-directional links between communications entities.